typedef int StackDate;
typedef struct Stack {
	StackDate* a;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* st);
void StackDestory(Stack* st);
void StackPush(Stack* st, StackDate x);
void StackPop(Stack* st);
StackDate StackTop(Stack* st);
bool StackEmpty(Stack* st);
int StackSize(Stack* st);
void StackInit(Stack* st)
{
	assert(st);
	st->a = NULL;
	st->top = st->capacity = 0;
}

void StackDestory(Stack* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->top = st->capacity = 0;
}
void StackPush(Stack* st, StackDate x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		StackDate* tmp = (StackDate*)realloc(st->a, newcapacity * sizeof(StackDate));
		if (tmp == NULL)
		{
			printf("relloc err\n");
			return;
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top] = x;
	st->top++;
}
void StackPop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}
StackDate StackTop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top-1];
}
bool StackEmpty(Stack* st)
{
	assert(st);
	return st->top == 0;
}
int StackSize(Stack* st)
{
	assert(st);
	return st->top;
}
/*
以 s={[()]} 为例说明：
创建一个空栈。
从左到右遍历 s。
1. s[0]={，这是一个左括号，入栈。
2. s[1]=[，这是一个左括号，入栈。
3. s[2]=(，这是一个左括号，入栈。
4. s[3]=)，这是一个右括号，它必须和栈顶的 ( 组成一对（消除），弹出栈顶。
5. s[4]=]，这是一个右括号，它必须和栈顶的 [ 组成一对（消除），弹出栈顶。
6. s[5]=}，这是一个右括号，它必须和栈顶的 { 组成一对（消除），弹出栈顶。
遍历结束，由于栈为空，说明所有括号均已匹配完毕，返回 true。反之，如果在遍历的过程中，发现栈为空，或者括号类型不匹配的情况，返回 false。此外，如果遍历结束栈不为空，说明还有没匹配的左括号，返回 false。
*/
//是左括号就入栈 不是做左括号就判断与栈顶是否匹配
bool isValid(char* s) {
    //优化：如果字符串个数为奇数，则不匹配
    int len = strlen(s);
    if(len%2 == 1) return false;
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' || *s == '{' || *s == '['){
            StackPush(&st, *s);
        }
        else if(StackEmpty(&st)){
            //栈为空，不匹配
            StackDestory(&st);
            return false;
        }
        else if((*s == ')' && StackTop(&st) != '(')
            || (*s == '}' && StackTop(&st) != '{')
            || (*s == ']' && StackTop(&st) != '[')
            ){
                StackDestory(&st);
                return false;
        }else StackPop(&st);
        ++s;
    }
    bool ret = StackEmpty(&st);
    StackDestory(&st);
    return ret;
}typedef int StackDate;
typedef struct Stack {
	StackDate* a;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* st);
void StackDestory(Stack* st);
void StackPush(Stack* st, StackDate x);
void StackPop(Stack* st);
StackDate StackTop(Stack* st);
bool StackEmpty(Stack* st);
int StackSize(Stack* st);
void StackInit(Stack* st)
{
	assert(st);
	st->a = NULL;
	st->top = st->capacity = 0;
}

void StackDestory(Stack* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->top = st->capacity = 0;
}
void StackPush(Stack* st, StackDate x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		StackDate* tmp = (StackDate*)realloc(st->a, newcapacity * sizeof(StackDate));
		if (tmp == NULL)
		{
			printf("relloc err\n");
			return;
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top] = x;
	st->top++;
}
void StackPop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}
StackDate StackTop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top-1];
}
bool StackEmpty(Stack* st)
{
	assert(st);
	return st->top == 0;
}
int StackSize(Stack* st)
{
	assert(st);
	return st->top;
}
/*
以 s={[()]} 为例说明：
创建一个空栈。
从左到右遍历 s。
1. s[0]={，这是一个左括号，入栈。
2. s[1]=[，这是一个左括号，入栈。
3. s[2]=(，这是一个左括号，入栈。
4. s[3]=)，这是一个右括号，它必须和栈顶的 ( 组成一对（消除），弹出栈顶。
5. s[4]=]，这是一个右括号，它必须和栈顶的 [ 组成一对（消除），弹出栈顶。
6. s[5]=}，这是一个右括号，它必须和栈顶的 { 组成一对（消除），弹出栈顶。
遍历结束，由于栈为空，说明所有括号均已匹配完毕，返回 true。反之，如果在遍历的过程中，发现栈为空，或者括号类型不匹配的情况，返回 false。此外，如果遍历结束栈不为空，说明还有没匹配的左括号，返回 false。
*/
//是左括号就入栈 不是做左括号就判断与栈顶是否匹配
bool isValid(char* s) {
    //优化：如果字符串个数为奇数，则不匹配
    int len = strlen(s);
    if(len%2 == 1) return false;
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' || *s == '{' || *s == '['){
            StackPush(&st, *s);
        }
        else if(StackEmpty(&st)){
            //栈为空，不匹配
            StackDestory(&st);
            return false;
        }
        else if((*s == ')' && StackTop(&st) != '(')
            || (*s == '}' && StackTop(&st) != '{')
            || (*s == ']' && StackTop(&st) != '[')
            ){
                StackDestory(&st);
                return false;
        }else StackPop(&st);
        ++s;
    }
    bool ret = StackEmpty(&st);
    StackDestory(&st);
    return ret;
}